package leetcode_二叉树;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 二叉树的中序遍历
 * 算法：栈、递归
 *
 * @author yezh
 * @date 2024/1/12 17:08
 */
public class _94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }

    void inorder(TreeNode node, List<Integer> ans) {
        if (node != null) {
            if (node.left != null) inorder(node.left, ans);
            ans.add(node.val);
            if (node.right != null) inorder(node.right, ans);
        }
    }

    public List<Integer> inorderTraversal_iteration(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        while (true) {
            while (root != null) {
                st.addFirst(root);
                root = root.left;
            }
            if (st.isEmpty()) break;
            root = st.pollFirst();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }

}
